package arithmetic_40;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 * @author wxh
 */
public class Solution_4 {

	/**
	 * 思路1：BFS解法 ->套用BFS模板代码（ali.Solution_5）
	 */
	public int minDepth(TreeNode root) {

		if (root == null) {
			return 0;
		}

		Queue<TreeNode> queue = new LinkedList();
		queue.offer(root);

		int minDepth = 0;
		while (!queue.isEmpty()) {
			int currentLevelSize = queue.size(); //从队列大小可以知道，当前层级有多少个元素
			++minDepth; // 深度+1
			for (int i = 0; i < currentLevelSize; i++) {
				// 获取并移除队头元素
				TreeNode treeNode = queue.poll();

				// 当第一个节点出现其左子树和右子树都为空时，说明这是第一个叶子节点，直接返回当前深度即可
				if (treeNode.left == null && treeNode.right == null) {
					return minDepth;
				}

				// 检查是否存在左右子节点，存在则入队列
				if (treeNode.left != null) {
					queue.offer(treeNode.left);
				}
				if (treeNode.right != null){
					queue.offer(treeNode.right);
				}
			}
		}
		return minDepth;
	}

	/**
	 * 思路2：DFS解法
	 */
	public int minDepth2(TreeNode root) {

		// 1、 特殊情况考虑
		if (root == null) {
			return 0;
		}

		// 如果没有左子树，则直接计算右子树的最小深度 + 1即可
		if (root.left == null) {
			return 1 + minDepth2(root.right); // + 1当前节点也要算一层
		}
		// 如果没有右子树，则直接计算左子树的最小深度 + 1即可
		if (root.right == null) {
			return 1 + minDepth2(root.left); // + 1当前节点也要算一层
		}

		//代码走到这里，说明root的左右子树都不为空

		// 2、DFS分治，分成两个子问题：1、左子树的最小深度，右子树的最小深度
		int leftMiniDepth = minDepth2(root.left);
		int rightMiniDepth = minDepth2(root.right);

		// 3、聚合子问题的结果：取左右子树的最小深度的较小值，加上当前节点（当前节点也要算一层）
		return 1 + Math.min(leftMiniDepth, rightMiniDepth);

	}

	/**
	 * 思路3：思路2更加简洁的写法
	 */
	public int minDepth3(TreeNode root) {

		if (root == null) {
			return 0;
		}

		// 1、分治
		int left = minDepth3(root.left);
		int right = minDepth3(root.right);

		/**
		 * 2、聚合子问题结果：
		 * 如果左或右子树为空，这种情况直接为：不为空子树+1
		 * 如果左右子树都不为空，则取最小值+1
		 */
		return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;

	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode() {}
		TreeNode(int val) { this.val = val; }
		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

}